Many data compressors, such as those based on the LZ77 compression algorithm, perform data compression by replacing repeated data strings in an input data stream with pointers to prior positions of the repeated strings in the input data stream. Data compression is achievable because the pointers are typically smaller than the repeated data strings they replace. To find the repeated data strings in an input data stream, some implementations of such data compressors utilize hash chain matching. In hash chain matching, a hash table is constructed with each entry corresponding to a respective data substring that was found previously in the input data stream. Each entry of the hash table points to a respective hash chain storing one or more prior positions (e.g., addresses) in the input data stream at which the particular data substring corresponding to the respective hash table entry was found. Data compressors utilize such hash chains to limit the number of prior positions in the input data buffer to be searched when attempting to find a prior data string that matches a current data string beginning at the current position of the input data stream undergoing compression.
The figures are not to scale. Wherever possible, the same reference numbers will be used throughout the drawing(s) and accompanying written description to refer to the same or like parts, elements, etc.